package 第七周;

/*
 * @author  YxinMiracle
 * @date  2022-05-06 9:43
 * @Gitee: https://gitee.com/yxinmiracle
 */

import java.util.ArrayList;
import java.util.Arrays;

public class 买卖股票的最佳时机 {

    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[] newPrices = new int[n + 1];
        newPrices[0] = 0;
        for (int i = 1; i <= n; i++) newPrices[i] = prices[i - 1];

        int[][][] f = new int[n + 1][2][2];
        Arrays.fill(f[0][1],-1000000);
        Arrays.fill(f[0][0],-1000000);
        f[0][0][0] = 0;
        for (int i = 1; i <= n; i++) {

            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 2; k++) {
                    f[i][j][0] = Math.max(f[i][j][0],f[i-1][j][k]);// 什么都不做
                    f[i][0][1] = Math.max(f[i][0][1],f[i-1][1][0]+newPrices[i]); // 卖掉
                    f[i][1][0] = Math.max(f[i][1][0],f[i-1][0][0]-newPrices[i]); // 买股票
                }
            }
        }
        return Math.max(f[n][0][1],f[n][0][0]);
    }

    public static void main(String[] args) {
        System.out.println(new 买卖股票的最佳时机().maxProfit(new int[]{1,2,3,4}));
    }


}
